package Tree;

public class Morris {
    public static void morris(TreeDP.Node head){
        if (head == null)return;

        TreeDP.Node cur = head;
        TreeDP.Node mostRight = null;
        while (cur != null){//主流程
            mostRight = cur.left;//mostRight 是 cur的左孩子
            if (mostRight != null){
                while (mostRight != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //mostRight 变成了cur左子树上,最右的节点
                if (mostRight.right == null){//第一次来到cur
                    mostRight.right =cur;
                    cur =cur.left;
                    continue;
                }else {//mostRight.right == cur
                    mostRight.right =null;
                }
            }
            cur = cur.right;

        }
    }
    public static void morrisPre(TreeDP.Node head){
        if (head == null)return;

        TreeDP.Node cur = head;
        TreeDP.Node mostRight = null;

        while (cur != null){//主流程
            mostRight = cur.left;//mostRight 是 cur的左孩子
            if (mostRight != null){
                while (mostRight != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //mostRight 变成了cur左子树上,最右的节点
                if (mostRight.right == null){//第一次来到cur,打印第一次出现
                    System.out.println(cur.value);
                    mostRight.right =cur;
                    cur =cur.left;
                    continue;
                }else {//mostRight.right == cur
                    mostRight.right =null;
                }
            }else {//没有左子树,只出现一次,直接打印
                System.out.println(cur.value);
            }
            cur = cur.right;

        }
    }
    public static void morrisIn(TreeDP.Node head){
        if (head == null)return;

        TreeDP.Node cur = head;
        TreeDP.Node mostRight = null;
        while (cur != null){//主流程
            mostRight = cur.left;//mostRight 是 cur的左孩子
            if (mostRight != null){
                while (mostRight != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //mostRight 变成了cur左子树上,最右的节点
                if (mostRight.right == null){//第一次来到cur
                    mostRight.right =cur;
                    cur =cur.left;
                    continue;
                }else {//mostRight.right == cur
                    mostRight.right =null;
                }
            }
            //没左树,直接打印 , 第一次会有continue 碰不到打印行为,第二次才会出来打印
            System.out.println(cur.value);
            cur = cur.right;
        }
    }
    public static void morrisPos(TreeDP.Node head){
        if (head == null)return;
        TreeDP.Node cur = head;
        TreeDP.Node mostRight = null;
        while (cur != null){//主流程
            mostRight = cur.left;//mostRight 是 cur的左孩子
            if (mostRight != null){
                while (mostRight != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                //mostRight 变成了cur左子树上,最右的节点
                if (mostRight.right == null){//第一次来到cur
                    mostRight.right =cur;
                    cur =cur.left;
                    continue;
                }else {//mostRight.right == cur
                    mostRight.right =null;
                    printEdge(cur.left);
                }
            }
            cur = cur.right;
        }
        printEdge(head);
        System.out.println();
    }
    public static void printEdge(TreeDP.Node x){
        TreeDP.Node tail = reverseEdge(x);
        TreeDP.Node cur = tail;
        while (cur != null){
            System.out.println(cur.value);
            cur = cur.right;
        }
        reverseEdge(tail);
    }
    public static TreeDP.Node reverseEdge(TreeDP.Node from){
        TreeDP.Node pre =null;
        TreeDP.Node cur =null;
        while (from != null){
            cur = from.right;
            from.right = pre;
            pre = from;
            from =cur;
        }
        return pre;
    }
}
